<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(A卷,200分)- 服务中心选址（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>一个快递公司希望在一条街道建立新的服务中心。公司统计了该街道中所有区域在地图上的位置&#xff0c;并希望能够以此为依据为新的服务中心选址&#xff1a;使服务中心到所有区域的距离的总和最小。</p> 
<p>给你一个数组positions&#xff0c;其中positions[i] &#61; [left, right] 表示第 i 个区域在街道上的位置&#xff0c;其中left代表区域的左侧的起点&#xff0c;right代表区域的右侧终点&#xff0c;假设服务中心的位置为location&#xff1a;</p> 
<ul><li>如果第 i 个区域的右侧终点right满足 right &lt; location&#xff0c;则第 i 个区域到服务中心的距离为 location - right&#xff1b;</li><li>如果第 i 个区域的左侧起点left 满足 left &gt; location&#xff0c;则第 i 个区域到服务中心的距离为left - location&#xff1b;</li><li>如果第 i 个区域的两侧left&#xff0c;right满足left &lt;&#61; location &lt;&#61; right&#xff0c;则第 i 个区域到服务中心的距离为0</li></ul> 
<p>选择最佳的服务中心位置为location&#xff0c;请返回最佳的服务中心位置到所有区域的距离总和的最小值。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>先输入区域数组positions的长度n&#xff08;1 ≤ n ≤ 10^5&#xff09;</p> 
<p>接下来 n 行每行输入成对的left和right值&#xff0c;以空格隔开</p> 
<ul><li>-10^9 &#xff1c;left ≤ 10^9</li><li>-10^9 &#xff1c;right ≤ 10^9</li></ul> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>输出为location</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">3<br /> 1 2<br /> 3 4<br /> 10 20</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">8</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">无</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">2<br /> 1 4<br /> 4 5</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">0</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">无</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">4<br /> 5 6<br /> 1 8<br /> 7 15<br /> 2 4</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">3</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">无</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:85px;">输入</td><td style="width:413px;">6<br /> 1 3<br /> 4 9<br /> 2 15<br /> 6 27<br /> 15 17<br /> 5 8</td></tr><tr><td style="width:85px;">输出</td><td style="width:413px;">12</td></tr><tr><td style="width:85px;">说明</td><td style="width:413px;">无</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">16<br /> 41 67<br /> 0 34<br /> 24 69<br /> 58 78<br /> 62 64<br /> 5 45<br /> 27 81<br /> 61 91<br /> 42 95<br /> 27 36<br /> 4 91<br /> 2 53<br /> 82 92<br /> 16 21<br /> 18 95<br /> 26 47</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">127</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">无</td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>根据网友反馈进行分析得出&#xff0c;本题中各区域应该是有交集的。</p> 
<p>我想了很久&#xff0c;如何求解某个点到有交集区域的最小距离和&#xff0c;但是没有什么好的办法&#xff0c;直到我死心准备用暴力法求解时&#xff0c;发现了一丝丝生机。下面是暴力法测试过程&#xff1a;</p> 
<p>测试用例&#xff1a;含区域交集情况</p> 
<blockquote> 
 <p>11<br /> -10 10<br /> 1 2<br /> 3 4<br /> 5 10<br /> 6 8<br /> 7 12<br /> 9 13<br /> 15 20<br /> 31 41<br /> 22 35<br /> 34 50</p> 
</blockquote> 
<p></p> 
<p>JavaScript暴力实现</p> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
let n;
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61;&#61; 1) {
    n &#61; lines[0] - 0;
  }

  if (n &amp;&amp; lines.length &#61;&#61;&#61; n &#43; 1) {
    const positions &#61; lines.slice(1).map((line) &#61;&gt; line.split(&#34; &#34;).map(Number));
    console.log(getResult(n, positions));
    lines.length &#61; 0;
  }
});

function getResult(n, positions) {
  const tmp &#61; positions.flat(2).sort((a, b) &#61;&gt; a - b);
  let min &#61; tmp.at(0);
  let max &#61; tmp.at(-1);
  let ans &#61; Infinity;

  for (let i &#61; min; i &lt;&#61; max; i &#43;&#61; 0.5) {
    let dis &#61; 0;
    for (let position of positions) {
      const [l, r] &#61; position;
      if (r &lt; i) dis &#43;&#61; i - r;
      else if (i &lt; l) dis &#43;&#61; l - i;
    }

    console.log(i, dis); // 服务中心选址 i 位置&#xff0c;dis为该位置服务中心到所有区间的距离之和

    ans &#61; Math.min(ans, dis);
  }

  return ans;
}
</code></pre> 
<p><img alt="" height="789" src="https://img-blog.csdnimg.cn/348df5492bd54af7a9a0cddd9dc82116.png" width="1200" /></p> 
<p>可以发现&#xff0c;当服务中心选址10位置时&#xff0c;到各区间距离之和最小为78 </p> 
<p></p> 
<p>Java暴力实现</p> 
<pre><code class="language-java">import java.util.ArrayList;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    int n &#61; sc.nextInt();

    double[][] positions &#61; new double[n][2];
    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
      positions[i][0] &#61; sc.nextInt();
      positions[i][1] &#61; sc.nextInt();
    }

    System.out.println(getResult(n, positions));
  }

  public static double getResult(int n, double[][] positions) {
    ArrayList&lt;Double&gt; tmp &#61; new ArrayList&lt;&gt;();
    for (double[] pos : positions) {
      tmp.add(pos[0]);
      tmp.add(pos[1]);
    }
    tmp.sort(Double::compareTo);

    double min &#61; tmp.get(0);
    double max &#61; tmp.get(tmp.size() - 1);
    double ans &#61; Double.MAX_VALUE;

    for (double i &#61; min; i &lt;&#61; max; i &#43;&#61; 0.5) {
      double dis &#61; 0;
      for (double[] pos : positions) {
        double l &#61; pos[0];
        double r &#61; pos[1];
        if (r &lt; i) dis &#43;&#61; i - r;
        else if (i &lt; l) dis &#43;&#61; l - i;
      }

      System.out.println(i &#43; &#34;\t&#34; &#43; dis);

      ans &#61; Math.min(ans, dis);
    }

    return ans;
  }
}
</code></pre> 
<p><img alt="" height="906" src="https://img-blog.csdnimg.cn/5192f2aaaeb1469eafc8f9e45b374ded.png" width="1113" /></p> 
<p> 可以发现&#xff0c;当服务中心选址10位置时&#xff0c;到各区间距离之和最小为78 </p> 
<p></p> 
<p>Python暴力实现</p> 
<pre><code class="language-python">import math
import sys

# 输入获取
n &#61; int(input())
positions &#61; [list(map(int, input().split())) for i in range(n)]


# 算法入口
def getResult(n, positions):
    tmp &#61; []
    for pos in positions:
        tmp.append(pos[0])
        tmp.append(pos[1])

    tmp.sort()

    minP &#61; tmp[0]
    maxP &#61; tmp[-1]

    ans &#61; sys.maxsize

    i &#61; minP
    while i &lt;&#61; maxP:
        dis &#61; 0

        for l, r in positions:
            if r &lt; i:
                dis &#43;&#61; i - r
            elif i &lt; l:
                dis &#43;&#61; l - i

        print(str(i) &#43; &#34;\t&#34; &#43; str(dis))

        ans &#61; min(ans, dis)
        i &#43;&#61; 0.5

    return ans


# 算法调用
print(getResult(n, positions))
</code></pre> 
<p><img alt="" height="887" src="https://img-blog.csdnimg.cn/469e9e3c60a54ed98f2cc6f10d7b5a0a.png" width="1141" /></p> 
<p> 可以发现&#xff0c;当服务中心选址10位置时&#xff0c;到各区间距离之和最小为78 </p> 
<p></p> 
<p>上面暴力法过程中&#xff0c;我首先获得了所有区间中最左边的点min&#xff0c;和最右边的点max&#xff0c;并遍历这两个点之间每一个点作为服务中心地址 i &#xff0c;并求每个服务中心地址到各区域的距离之和 dis&#xff0c;然后将它们成对打印出来&#xff0c;结果发现一个现象&#xff1a;</p> 
<p><img alt="" height="386" src="https://img-blog.csdnimg.cn/71190894fbad43f1be61f0994a9d8975.png" width="478" /></p> 
<p>随着 服务中心位置 i 的变化&#xff0c;服务中心到各区域的距离之和 dis 呈现上图U型曲线。</p> 
<p>即&#xff0c;一定存在一个 i &#xff0c;其左边点 i-0.5 的&#xff0c;和其右边点 i&#43;0.5 到各区域的距离和大于它。</p> 
<p></p> 
<p>因此&#xff0c;我想是否可以用二分法求解&#xff0c;即取min点和max点的中间点mid作为服务中心位置&#xff0c;&#xff1a;</p> 
<ol><li>如果 dis(mid - 0.5)  &gt;&#61; dis(mid)  &amp;&amp; dis(mid&#43;0.5) &gt;&#61; dis(mid)&#xff0c;则 mid 就是所求的点</li><li>如果 dis(mid - 0.5 ) &gt; dis(mid) &gt; dis(mid &#43;0.5)&#xff0c;则说明当前 mid 点处于上图的下降区间&#xff0c;此时我们应该将mid作为新的min值&#xff0c;然后重新取min&#xff0c;max的中间点作为新mid</li><li>如果 dis(mid - 0.5 ) &lt; dis(mid) &lt; dis(mid &#43;0.5)&#xff0c;则说明当前 mid 点处于上图的上升区间&#xff0c;此时我们应该将mid作为新的max值&#xff0c;然后重新取min&#xff0c;max的中间点作为新mid</li></ol> 
<p>这样一搞&#xff0c;我们最终就可以找到最低dis的mid点。</p> 
<p></p> 
<hr /> 
<p>2023.04.12 上面的二分策略存在问题&#xff0c;本题要求解凹函数的极值&#xff0c;应该使用三分法求解。</p> 
<p>关于三分法请看&#xff1a;<a href="https://blog.csdn.net/qfc_128220/article/details/130097676" title="https://blog.csdn.net/qfc_128220/article/details/130097676">https://blog.csdn.net/qfc_128220/article/details/130097676</a></p> 
<p></p> 
<hr /> 
<p>2023.04.19  今天又有考友考到这题了&#xff0c;上面解法还是27%通过率。我已经emo了。</p> 
<p>然后我又读了一遍题目&#xff0c;发现&#xff1a;</p> 
<ul><li>题目描述&#xff1a;请返回最佳的服务中心位置到所有区域的距离总和的最小值</li><li>输出描述&#xff1a;输出为location</li><li>用例&#xff1a;输出的是最佳的服务中心位置到所有区域的距离总和的最小值</li></ul> 
<p>难道实际机试系统要求输出的是&#xff1a;服务中心的位置&#xff1f;</p> 
<p></p> 
<h4>JavaScript算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
let n, positions;
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61;&#61; 1) {
    n &#61; lines[0] - 0;
  }

  if (n &amp;&amp; lines.length &#61;&#61;&#61; n &#43; 1) {
    positions &#61; lines.slice(1).map((line) &#61;&gt; line.split(&#34; &#34;).map(Number));
    console.log(getResult(n, positions));
    lines.length &#61; 0;
  }
});

function getResult() {
  const tmp &#61; positions.flat(2).sort((a, b) &#61;&gt; a - b);

  let l &#61; tmp.at(0);
  let r &#61; tmp.at(-1);
  const eps &#61; 1e-5;

  while (r - l &gt;&#61; eps) {
    const k &#61; (r - l) / 3;
    const ml &#61; l &#43; k;
    const mr &#61; r - k;

    if (getDistance(ml) &lt; getDistance(mr)) {
      r &#61; mr;
    } else {
      l &#61; ml;
    }
  }

  return Math.floor(getDistance(l));
}

function getDistance(t) {
  let dis &#61; 0;
  for (let [l, r] of positions) {
    if (r &lt; t) dis &#43;&#61; t - r;
    else if (t &lt; l) dis &#43;&#61; l - t;
  }
  return dis;
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.ArrayList;
import java.util.Scanner;

public class Main {
  static double[][] positions;

  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    int n &#61; sc.nextInt();

    positions &#61; new double[n][2];
    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
      positions[i][0] &#61; sc.nextDouble();
      positions[i][1] &#61; sc.nextDouble();
    }

    System.out.println(getResult());
  }

  public static int getResult() {
    ArrayList&lt;Double&gt; tmp &#61; new ArrayList&lt;&gt;();
    for (double[] pos : positions) {
      tmp.add(pos[0]);
      tmp.add(pos[1]);
    }
    tmp.sort(Double::compareTo);

    double l &#61; tmp.get(0);
    double r &#61; tmp.get(tmp.size() - 1);
    double eps &#61; 1e-5;

    while (r - l &gt;&#61; eps) {
      double k &#61; (r - l) / 3;
      double ml &#61; l &#43; k;
      double mr &#61; r - k;

      if (getDistance(ml) &lt; getDistance(mr)) {
        r &#61; mr;
      } else {
        l &#61; ml;
      }
    }

    return (int) getDistance(l);
  }

  public static double getDistance(double t) {
    double dis &#61; 0;
    for (double[] pos : positions) {
      double l &#61; pos[0];
      double r &#61; pos[1];
      if (r &lt; t) dis &#43;&#61; t - r;
      else if (t &lt; l) dis &#43;&#61; l - t;
    }
    return dis;
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python">import math

# 输入获取
n &#61; int(input())
positions &#61; [list(map(float, input().split())) for _ in range(n)]


# 算法入口
def getResult():
    tmp &#61; []
    for pos in positions:
        tmp.extend(pos)
    tmp.sort()

    l &#61; tmp[0]
    r &#61; tmp[-1]
    eps &#61; 1e-5

    while r - l &gt;&#61; eps:
        k &#61; (r - l) / 3
        ml &#61; l &#43; k
        mr &#61; r - k

        if getDistance(ml) &lt; getDistance(mr):
            r &#61; mr
        else:
            l &#61; ml

    return int(getDistance(l))


def getDistance(t):
    dis &#61; 0
    for l, r in positions:
        if r &lt; t:
            dis &#43;&#61; t - r
        elif t &lt; l:
            dis &#43;&#61; l - t
    return dis


# 算法调用
print(getResult())
</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>